package pers.whj.util.graph;

import pers.whj.util.list.MinHeap;
import pers.whj.util.set.UFSet;

public class WeiGraphLink<T, E> extends GraphLink<T> implements WeiGraph<T, E>, WeiGraphOp<T, E> {
    public WeiGraphLink() {
        super();
    }

    public WeiGraphLink(int maxVertices) {
        super(maxVertices);
    }

    @Override
    @SuppressWarnings({"unchecked"})
    public E getWeight(int v1, int v2) {
        checkIfVerticesExist(v1, v2);
        GraphLink.Edge p = vertex(v1).adj;
        while (p != null && p.dest != v2) {
            p = p.next;
        }
        if (p != null) {
            return ((Edge<E>) p).weight;
        }
        return null;
    }

    @Override
    public E getWeight(T vertex1, T vertex2) {
        return getWeight(getPosition(vertex1), getPosition(vertex2));
    }

    @Override
    @SuppressWarnings({"unchecked"})
    public void setWeight(int v1, int v2, E weight) {
        checkIfVerticesExist(v1, v2);
        GraphLink.Edge p = vertex(v1).adj;
        while (p != null && p.dest != v2) {
            p = p.next;
        }
        if (p != null) {
            ((Edge<E>) p).weight = weight;
        }
    }

    @Override
    public void setWeight(T vertex1, T vertex2, E weight) {
        setWeight(getPosition(vertex1), getPosition(vertex2), weight);
    }

    @Override
    public boolean insertEdge(int v1, int v2) {
        return insertEdge(v1, v2, null);
    }

    @Override
    public boolean insertEdge(T vertex1, T vertex2) {
        return insertEdge(getPosition(vertex1), getPosition(vertex2), null);
    }

    @Override
    @SuppressWarnings({"unchecked"})
    public boolean insertEdge(int v1, int v2, E weight) {
        checkIfVerticesExist(v1, v2);
        if (v1 == v2) {
            return false;
        }
        GraphLink.Edge p = vertex(v1).adj;
        while (p != null && p.dest != v2) {
            p = p.next;
        }
        if (p != null) {
            return false;
        }
        //p = new GraphLink.Edge(v2, vertex(v1).adj);
        p = new Edge<>(v2, weight, (Edge<E>) vertex(v1).adj);
        vertex(v1).adj = p;
        //vertex(v2).adj = new GraphLink.Edge(v1, vertex(v2).adj);
        vertex(v2).adj = new Edge<>(v1, weight, (Edge<E>) vertex(v2).adj);
        mNumEdges++;
        return true;
    }

    @Override
    public boolean insertEdge(T vertex1, T vertex2, E weight) {
        return insertEdge(getPosition(vertex1), getPosition(vertex2), weight);
    }

    @Override
    public void getMinSpanTreeByKruskal(MinSpanTree<E> minSpanTree) {
        if (minSpanTree != null && isConnectedGraph()) {
            MinHeap<MinSpanTree.Edge<E>> heap = new MinHeap<>();
            UFSet ufSets = new UFSet(mNumVertices);
            int i, j;
            for (i = 0; i < mNumVertices; i++) {
                for (j = i + 1; j < mNumVertices; j++) {
                    E weight = getWeight(i, j);
                    if (weight != null) {
                        heap.insert(new MinSpanTree.Edge<>(i, j, weight));
                    }
                }
            }
            int counts = 1;
            MinSpanTree.Edge<E> edge;
            while (counts < mNumVertices) {
                edge = heap.delete();
                i = ufSets.find(edge.head);
                j = ufSets.find(edge.tail);
                if (i != j) {
                    ufSets.weightedUnion(i, j);
                    minSpanTree.add(edge);
                    counts++;
                }
            }
        }
    }

    @Override
    public void getMinSpanTreeByPrim(MinSpanTree<E> minSpanTree, int v) {
        if (minSpanTree == null || !isConnectedGraph()) {
            return;
        }
        checkIfVertexExists(v);
        boolean[] vertices = new boolean[mNumVertices];
        vertices[v] = true;
        MinHeap<MinSpanTree.Edge<E>> heap = new MinHeap<>();
        int u;
        int counts = 1;
        do {
            u = getFirstNeighbor(v);
            while (u != -1) {
                if (!vertices[u]) {
                    heap.insert(new MinSpanTree.Edge<>(v, u, getWeight(v, u)));
                }
                u = getNextNeighbor(v, u);
            }
            while (!heap.isEmpty() && counts < mNumVertices) {
                MinSpanTree.Edge<E> edge = heap.delete();
                if (!vertices[edge.tail]) {
                    minSpanTree.add(edge);
                    v = edge.tail;
                    vertices[v] = true;
                    counts++;
                    break;
                }
            }
        } while (counts < mNumVertices);
    }

    @Override
    public void getMinSpanTreeByPrim(MinSpanTree<E> minSpanTree, T vertex) {
        getMinSpanTreeByPrim(minSpanTree, getPosition(vertex));
    }

    protected static class Edge<E> extends GraphLink.Edge {
        // the cost int this edge
        E weight;

        public Edge(int dest, E weight, Edge<E> next) {
            super(dest, next);
            this.weight = weight;
        }
    }
}